package com.matt.insertionsort;

import java.util.Arrays;

public class ArraySort 
{

	public void insertionSort(int[] data)
	{
		long startTime = System.currentTimeMillis();
		
		for(int j = 1; j < data.length; j++)
		{
			int key = data[j];
			
			int i;
			for(i = j-1; i >= 0 && data[i] > key; i--)
			{
				data[i+1] = data[i];
			}
			
			data[i+1] = key;
		}
		
		System.out.println("amount of time to sort: " + (System.currentTimeMillis() - startTime));
	}
	
	public void mergeSort(int[] data, int first, int last)
	{
		if(first < last)
		{
			int q = (int) Math.floor((first + last) / 2);
			mergeSort(data, first, q);
			mergeSort(data, q + 1, last);
			merge(data, first, q, last);
		}
	}
	
	public void merge(int[] data, int first, int mid, int last)
	{
		mid = data.length / 2;
		
		int[] leftArr = Arrays.copyOfRange(data, 0, mid);
		int[] rightArr = Arrays.copyOfRange(data, mid, data.length);
		
		int i = 1;
		int j = 1;
		
		System.out.println("left arr length: " + leftArr.length);
		System.out.println("right arr length: " + rightArr.length);
		for(int k = 0; k < (data.length)-1; k++)
		{
			if(leftArr[i] <= rightArr[j])
			{
				data[k] = leftArr[i];
				i++;
			}
			else
			{
				data[k] = rightArr[j];
				j++;
			}
		}
	}
}
